package java学习.leetcode.editor.cn;
/**
 * @author 刘世锦
 * 2022-12-31 11:50:26	 当前时间
 */
//给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 
//
// 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（
//一个节点也可以是它自己的祖先）。” 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
//输出：3
//解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
// 
//
// 示例 2： 
//
// 
//输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
//输出：5
//解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
// 
//
// 示例 3： 
//
// 
//输入：root = [1,2], p = 1, q = 2
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 树中节点数目在范围 [2, 105] 内。 
// -109 <= Node.val <= 109 
// 所有 Node.val 互不相同 。 
// p != q 
// p 和 q 均存在于给定的二叉树中。 
// 
// Related Topics 树 深度优先搜索 二叉树 
// 👍 2083 👎 0

public class 二叉树的最近公共祖先{
	public static void main(String[] args) {
		Solution solution = new 二叉树的最近公共祖先().new Solution();
		TreeNode root = new TreeNode(6);
		TreeNode node1 = new TreeNode(4);
		TreeNode node2 = new TreeNode(7);
		TreeNode node3 = new TreeNode(3);
		TreeNode node4 = new TreeNode(1);
		TreeNode node5 = new TreeNode(8);
		root.left = node1; root.right = node2;
		node1.left = node3; node1.right = node4;
		node2.right = node5;
		node3.left = null; node3.right  = null;
		node4.left = null; node4.right  = null;
		System.out.println(solution.lowestCommonAncestor(root,node3,node1));
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {


	/** 复习  @author 刘世锦
	 *  @date  2023/2/11 21:25
	 */

	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		// 因为root从上往下遍历，
		// 若 root遍历到p 说明 p为q的祖先节点 ，反之，依然，
		if (root==null||root==q||root==p){
			return root;
		}

		TreeNode left = lowestCommonAncestor(root.left, p, q);
		TreeNode right = lowestCommonAncestor(root.right, p, q);
		// 左右子树都不为空，说明p,q分散于root的两侧
		if (left!=null&&right!=null){
			return root;
		}else if (left==null){
			return right;
		}else {
			return left;
		}






	}

	// 复习end

	/**
	 * 遍历方式： 寻找节点的父节点，自下而上：后序 左右中
	 *  一个节点也可以是它自己的祖先！
	 *
	 *  因此：
	 * (1) 若 root==null || root == q || root == p
	 *       叶子节点	        找到q          找到p
	 *     	 直接返回.
	 *     考虑掉了 root为空的情况
	 * (2) 开始依次遍历左右子树：
	 *  	1. left!=null && right!=null  在左右子树分别找到，说明p,q分散于左右子树，故最近公共祖先就是root
	 *  	2. left!=null && right==null  root的右子树没有p、q ,说明在左子树找到了pq
	 *  	3. left==null && right!=null  反之，在右子树找到了pq
	 *  	4. 都为空 说明 没有找到p、q
	 *
	 */
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
    	if (root==null || root == q || root == p){
        	return root;
		}
    	TreeNode left = lowestCommonAncestor(root.left,p,q);
    	TreeNode right = lowestCommonAncestor(root.right,p,q);
    	if (left!=null&&right!=null){
    		return root;
		}else if (left!=null && right==null){
    		return left;
		}else{
    		return right;
		}

    }






	public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
		if (root==null||root==p||root==q){
			return root;
		}

		TreeNode left = lowestCommonAncestor(root.left,p,q);
		TreeNode right = lowestCommonAncestor(root.right,p,q);
		if (left!=null&&right!=null){
			return root;
		}else if (left!=null){
			return left;
		}else{
			return right;
		}

	}

	}
//leetcode submit region end(Prohibit modification and deletion)

}
